package com.huawei.su;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class BM3 {


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        reverseKGroup(listNode1, 3);
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        //遍历 输入链表
        ListNode index1 = head;
        ListNode index2 = head;
        ListNode index3 = null;
        ListNode result = null;
        int counter = 1;
        //入栈
        Stack<ListNode> stack = new Stack<>();

        while (true) {
            if (index1 == null) {
                index3.next = null;
                break;
            }
            stack.push(index2);

            if (counter % k == 0) {
                index3 = stack.pop();
                if(result == null){
                    result = index3;
                }

                while (true){
                    if(stack.isEmpty()){
                        break;
                    }
                    index3.next = stack.pop();
                    index3 = index3.next;
                }

            }

            index1 = index1.next;
            index2 = index1;
            counter++;
        }
        return result;
    }

    public static ListNode reverseKGroup1(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode index1 = head;
        List<ListNode> list = new ArrayList<>();
        int counter = 0;

        while (true) {
            if (index1 == null) {
                break;
            }
            if (counter % k == 0) {
                list.add(index1);
            }
            counter++;
            index1 = index1.next;
        }

        if (list.size() == 1 && counter < k) {
            return head;
        }
        counter = 0;
        for (ListNode listNode : list) {
            ListNode index2 = listNode;
            while (true) {
                if (index2 == null) {
                    break;
                }
                if (counter % k + 1 == k) {
                    index2.next = null;
                }
                counter++;
                index2 = index2.next;
            }
        }

        //遍历反转链表
        List<ListNode> newList = new ArrayList<>();
        for (ListNode listNode : list) {
            ListNode index3 = listNode;
            Stack<ListNode> stack = new Stack<>();
            while (true) {
                if (index3 == null) {
                    break;
                }
                stack.push(index3);
                index3 = index3.next;
            }
            ListNode newHead = stack.pop();
            ListNode index4 = newHead;
            while (true) {
                if (stack.isEmpty()) {
                    index4.next = null;
                    break;
                }
                index4.next = stack.pop();
                index4 = index4.next;
            }
            newList.add(newHead);
        }
        if (newList.size() > 1) {
            ListNode index = newList.get(0);
            int i = 1;
            while (true) {
                if (index.next == null) {
                    index.next = newList.get(i);
                    i++;
                    if (i >= newList.size()) {
                        break;
                    }
                }
                index = index.next;
            }
        }
        return newList.get(0);
    }
}
